package com.leetcode.No0032;

import org.junit.Test;

/**
 * @program: leetcode
 * @description: 最长有效括号 dp
 * @author: wangzhihua
 * @date: 2021-06-27
 */
public class Solution02 {
	@Test
	public void test01() {
//		System.out.println(longestValidParentheses("()()()"));
		System.out.println(longestValidParentheses("(()()(())(("));
	}

	public int longestValidParentheses(String s) {
		int len = s.length();
		char[] brackets = s.toCharArray();
		int[] dp = new int[len];
		int ans = 0;

		for (int i = 0; i < len; ++i) {
			if (brackets[i] == '(') {
				continue;
			}
			if (brackets[i] == ')' && i > 0) {
				if (brackets[i - 1] == '(') {
					dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
				} else if (i - dp[i - 1] - 1 >= 0 && brackets[i - dp[i - 1] - 1] == '(') {
					dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 > 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
				}
				ans = Math.max(ans, dp[i]);
			}
		}

		return ans;
	}

}
